package gold.gold02;

import java.util.*;

/**
 * 树, 递归, 生成, 排列组合
 * 如果只是数有多少种方法的话, 可以用左子树的方法数*右子树的方法数*C[[a] [a+b]],
 * a为左子树节点数, b为右子树节点数, C是排列组合, a+b个球里放a个球有几种放法, 球都一样。
 * 验证为正确。
 */
public class S0409二叉搜索树序列_所有可生成序列 {

    /**
     * 13, 回溯法, 总时间都不长, 没有长用例。
     * 因为他是要存到一个List<List<Integer>>里面的, 所以时间复杂度肯定很高
     */
    // 统计一下总数
    public int nodeNums = 0;
    public List<List<Integer>> res;
    public List<List<Integer>> BSTSequences2(TreeNode root) {
        res = new LinkedList<List<Integer>>();
        if(root == null){
            res.add(new ArrayList<>());
            return res;
        }
        List<Integer> curRoute = new LinkedList<>();
        Set<TreeNode> selectSet = new HashSet<>();
        // 这里用线程安全集合也不行, 用set和list都一样。
        // Set<TreeNode> selectSet = Collections.synchronizedSet(new HashSet<>());
        selectSet.add(root);
        getCount(root);
        BSTSequencesHelp(root, curRoute, 1, selectSet);
        return res;

    }
    // 注意每次往下推的时候, 候选的是set里的所有值, 也就是塞进去一个, 下一层就多了他的两个子节点候选
    public void BSTSequencesHelp(TreeNode root, List<Integer> curRoute, int curPosi, Set<TreeNode> selectSet){
        if(root == null) return ;
        // System.out.println(root.val + "  curPosi " + curPosi);
        if(curPosi == nodeNums){
            // 创建时直接传Collection进去
            List<Integer> temp = new LinkedList<>(curRoute);
            temp.add(root.val);
            res.add(temp);
            // System.out.println(temp);
            return;
        }
        curRoute.add(root.val);
        selectSet.add(root.left);
        selectSet.add(root.right);
        selectSet.remove(root); // 候选set删除自己
        for(TreeNode node: selectSet){
            // 这样边遍历边修改会有问题, 用一个新set往下传, 需要想办法除了这一层复制
            Set<TreeNode> passSet = new HashSet<>(selectSet);
            BSTSequencesHelp(node, curRoute, curPosi + 1, passSet);
        }
        curRoute.remove(curRoute.size() - 1);

    }
    public void getCount(TreeNode root){
        if(root != null){
            nodeNums ++;
            getCount(root.left);
            getCount(root.right);
        }

    }

    /**
     * 别人的做法, 和我上面想法一样, 但是不用那个set传递下一层的东西
     * 双向队列deque好用
     * 要学习这个, 查看对dq的每一次操作, 就知道他是怎么回溯的了
     */
    // 这两个声明成全局变量，这也回溯函数就少传点参数
    private LinkedList<Integer> path = new LinkedList<>();
    private List<List<Integer>> result = new LinkedList<>();

    public List<List<Integer>> BSTSequences3(TreeNode root) {
        Deque<TreeNode> dq = new LinkedList<>();
        if (root != null) {
            dq.offer(root);
        }
        dfs(dq);
        return result;
    }

    // 1.确定递归函数返回值和参数
    public void dfs(Deque<TreeNode> dq) {
        // 2.确定递归终止条件
        // dq是该层剩下可选节点的候选队列，若队列为空，则说明没有候选元素了
        // 因此可直接把当前路径添加到结果集，然后返回
        if (dq.isEmpty()) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        //3.确定回溯函数的遍历过程
        // 当前层可与选择的候选节点的个数
        int size = dq.size();
        // 注意这个size, 只是用来计数的
        while(size > 0) {
            TreeNode cur = dq.pollFirst();
            // 向路径中添加当前值
            path.add(cur.val);
            // 记录添加的子节点数量，等会回溯时需要用
            int children = 0;
            // 向候选队列中添加子节点
            if (cur.left != null) {
                children++;
                dq.offerLast(cur.left);
            }
            if (cur.right != null) {
                children++;
                dq.offerLast(cur.right);
            }
            // 递归
            dfs(dq);
            // 回溯候选队列
            while (children > 0) {
                dq.pollLast();
                children--;
            }
            dq.offerLast(cur);
            // 回溯路径
            path.removeLast();
            // 当前节点处理完毕，数量减一
            size--;
        }
    }




    /**
     * 没写出来, 用上面的计数的想法, 使用左子树的生成数组和右子树的生成数组, 创建新的生成数组
     */
    public List<List<Integer>> BSTSequences(TreeNode root) {
        if(root == null) return null;
        List<List<Integer>> leftList = BSTSequences(root.left);
        List<List<Integer>> rightList = BSTSequences(root.right);
        List<List<Integer>> resultList = new ArrayList<>();

        if(leftList == null){
            if(rightList == null){
                // 左右子树都为空
                List<Integer> temp1 = new ArrayList<>();
                temp1.add(root.val);
                resultList.add(temp1);
                return resultList;
            }else{
                // 左空右不为空
                for(List<Integer> temp1: rightList){
                    // 看, 这个返回的是void, 无法通过肉眼看出来错误, 必须注意
                    // temp1 = temp1.add(0, root.val);
                    temp1.add(0, root.val);
                    resultList.add(temp1);
                }
                return resultList;
            }
        }else{
            if(rightList == null){
                // 左不空右空
                for(List<Integer> temp1: leftList){
                    temp1.add(0, root.val);
                    resultList.add(temp1);
                }
                return resultList;
            }else{
                // 左右都不空
                for(List<Integer> temp1: leftList){
                    for(List<Integer> temp2: rightList){

                    }
                }
                return resultList;
            }
        }
    }
}